package 剑指offer;


import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * @author: tyy 剑指 Offer
 * 1005. K 次取反后最大化的数组和
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
示例 1：
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。
 * @create: 2021-11-28 17:40
 * @description:
 **/
public class Solution35 {

    /**
     * 贪心算法
     * @param nums
     * @param K
     * @return
     */
    public int largestSumAfterKNegations(int[] nums, int K) {
        // 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
        nums = IntStream.of(nums)
                .boxed()
                .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
                .mapToInt(Integer::intValue).toArray();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            //从前向后遍历，遇到负数将其变为正数，同时K--
            if (nums[i] < 0 && K > 0) {
                nums[i] = -nums[i];
                K--;
            }
        }
        // 如果K还大于0，那么反复转变数值最小的元素，将K用完
        if (K % 2 == 1) nums[len - 1] = -nums[len - 1];
        return Arrays.stream(nums).sum();

    }

    /** 暴力破解
     * @param nums
     * @param k
     * @return
     */
    public int largestSumAfterKNegations1(int[] nums, int k) {
        // 按大小排序
        int count = 0; // 小于0的个数
        for(int i=0;i<nums.length;i++) {
            if (nums[i] < 0) {
                count++;
            }
        }
        for(int i=0;i<nums.length-1;i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        //
        int sum = 0;
        if (count >= k) {
            // all
            for (int i = 0; i < nums.length; i++) {
                if (i >=k) {
                    sum += nums[i];
                    continue;
                }
                sum -=nums[i];
            }
        }
        else if (count < k) {
            int n = k - count;
            if (n%2 == 0) {
                for (int i = 0; i < nums.length; i++) {
                    sum += Math.abs(nums[i]);
                }
            }else{
                //两种情况，1、0
                for (int i = 0; i < nums.length; i++) {
                    sum += Math.abs(nums[i]);
                }
                if (count == nums.length) {
                    return sum + 2 * nums[count-1];
                }
                if (nums[count] == 0) {
                    return sum;
                }
                if (count == 0) {
                    sum = sum - 2 * nums[0];
                    return sum;
                }
                int num = -nums[count];
                int num1 = nums[count-1];
                int min = Math.max(num, num1);
                sum = sum + 2 * min;
            }
        }
        return sum;
    }
    public static void main(String[] args) {
        Solution35 solution26 = new Solution35();
        int[] nums={-4,-2,-3};
        int k = 4;
//        int[] nums={-8,3,-5,-3,-5,-2};
//        int k = 6;
//        int[] nums={-2,5,0,2,-2};
//        int k = 3;
//        int[] nums={5,6,9,-3,3};
//        int k = 2;
//        int[] nums={2,-3,-1,5,-4};
//        int k = 2;
//        int[] nums={3,-1,0,2};
//        int k = 3;
//        int[] nums={4,2,3};
//        int k = 1;
        int num = solution26.largestSumAfterKNegations(nums, k);
        System.out.println("num = " + num);

    }
}
